void summary_init(SUMMARY *s, uint8_t type, uint8_t options)
{                                        // initialize summary structure
  if (s == NULL)
    return;

  if (type == SUMMARY_COUNTHISTOGRAM)
  {
    if (options > SUMMARY_LEN)           // options in the case of historgrams is the number of buckets
      options = SUMMARY_LEN;
    else if (options < 1)
      options = 1;
  } else if (type == SUMMARY_EXISTHISTOGRAM)
  {
    if (options > SUMMARY_LEN*8)
      options = SUMMARY_LEN*8;
    else if (options < 1)
      options = 1;
  }
    
  s->type = type;
  s->options = options;

  s->count = 0;
  memset(s->summary, 0, sizeof(s->summary));
}

void summary_addbv(SUMMARY *s, SUMMARY_VALUE v)  // add element to Bloom filter
{
  SUMMARY_VALUE t;

  v = VALUE_SHUFFLE(v);
  t = (v >> 8) % SUMMARY_PRIME1;
  BV_SET((uint8_t *) s->summary, t, 1);
  t = (v & 0xff) % SUMMARY_PRIME2;
  BV_SET((uint8_t *) s->summary, t, 1);
}

void summary_addrtree(SUMMARY *s, SUMMARY_VALUE v)      // add element to RTree
{
  uint8_t x, y, a, b, c, d;

  x = v & 0xff; y = v >> 8;
  a = s->summary[0] & 0xff; b = s->summary[0] >> 8;
  c = s->summary[1] & 0xff; d = s->summary[1] >> 8;

  if (s->count == 0)
  {
    a = x; b = y;
    c = x; d = y;
  } else {
    if (x < a)
      a = x;
    if (x > c)
      c = x;
    if (y < b)
      b = y;
    if (y > d)
      d = y;
  }
  
  s->summary[0] = a | (b << 8);
  s->summary[1] = c | (d << 8);
}

void histogram_normalize(SUMMARY *s)   // couting histogram: divide buckets greater than 1 by 2
{
  int i;

  for (i = 0; i < SUMMARY_SIZE; i++)
    if (((uint8_t *) s->summary)[i] > 1)
      ((uint8_t *) s->summary)[i] >>= 1;
}

void summary_addchistogram(SUMMARY *s, SUMMARY_VALUE v)   // add an element to a counting histogram 
{
  uint8_t bucket_index = v / s->options;

  if (bucket_index > SUMMARY_SIZE)
    bucket_index = SUMMARY_SIZE;

  if (((uint8_t *) s->summary)[bucket_index] == 0xff)
    histogram_normalize(s);

  ((uint8_t *) s->summary)[bucket_index]++; 
}

void summary_addehistogram(SUMMARY *s, SUMMARY_VALUE v)  // add an element to an exist historgram
{
  uint8_t bucket_index = v / s->options;

  if (bucket_index > SUMMARY_SIZE*8)
    bucket_index = SUMMARY_SIZE*8;
  BV_SET((uint8_t *) s->summary, bucket_index, 1);
}

void summary_addel(SUMMARY *s, SUMMARY_VALUE v)      // generic summary add element
{
  switch (s->type)
  {
    case SUMMARY_BLOOMFILTER:    summary_addbv(s, v);         break;
    case SUMMARY_RTREE:          summary_addrtree(s, v);      break;
    case SUMMARY_COUNTHISTOGRAM: summary_addchistogram(s, v); break;
    case SUMMARY_EXISTHISTOGRAM: summary_addehistogram(s, v); break;
  }

  s->count++;  
}

uint8_t summary_testlist(SUMMARY *s, SUMMARY_VALUE v)       // test if an element appears in a list summary
{
  int i;

  for (i = 0; i < s->count; i++)
    if (s->summary[i] == v)
      return 1;

  return 0;
}

uint8_t summary_testbv(SUMMARY *s, SUMMARY_VALUE v, uint16_t options)   // test if an element is in a Bloom filter
{
  SUMMARY_VALUE t;

  v = VALUE_SHUFFLE(v);
  t = (v >> 8) % SUMMARY_PRIME1;

  if (BV_GET((uint8_t *) s->summary, t))
  {
    t = (v & 0xff) % SUMMARY_PRIME2;
    return BV_GET((uint8_t *) s->summary, t);
  } else
    return 0;
}

uint8_t summary_testrtree(SUMMARY *s, SUMMARY_VALUE v, uint16_t options)   // test if an element is in RTree
{
  int i, r = options, a, b, x = v & 0xff, y = v >> 8;

  if (s->count <= SUMMARY_LEN)
  {
    for (i = 0; i < s->count; i++)
    {
      a = s->summary[i] & 0xff; b = s->summary[i] >> 8;
      if (x-r <= a && a <= x+r && y-r <= b && b <= y+r)
        return 1;
    }
    
    return 0;
  }

  return (x-r <= (s->summary[1] & 0xff) && x+r >= (s->summary[0] & 0xff) &&
    y-r <= (s->summary[1] >> 8) && y+r >= (s->summary[0] >> 8));
}

uint8_t summary_testchistogram(SUMMARY *s, SUMMARY_VALUE v, uint16_t options)   // test if an element is in counting histogram
{
  uint8_t bucket_index = v / s->options;

  if (bucket_index > SUMMARY_SIZE)
    bucket_index = SUMMARY_SIZE;

  return ((uint8_t *) s->summary)[bucket_index] > 0;
}

uint8_t summary_testehistogram(SUMMARY *s, SUMMARY_VALUE v, uint16_t options)    // test if an element is in exist historgram
{
  uint8_t bucket_index = v / s->options;

  if (bucket_index > SUMMARY_SIZE*8)
    bucket_index = SUMMARY_SIZE*8;

  return BV_GET((uint8_t *) s->summary, bucket_index);
}

uint8_t summary_test(SUMMARY *s, SUMMARY_VALUE v, uint16_t options)  // generic summary test
{
  if (s == NULL)
    return 0;

  if (s->count <= SUMMARY_LEN && s->type != SUMMARY_RTREE)
    return summary_testlist(s, v);

  switch (s->type)
  {
    case SUMMARY_BLOOMFILTER:    return summary_testbv(s, v, options);
    case SUMMARY_RTREE:          return summary_testrtree(s, v, options);
    case SUMMARY_COUNTHISTOGRAM: return summary_testchistogram(s, v, options);
    case SUMMARY_EXISTHISTOGRAM: return summary_testehistogram(s, v, options);
    default:                  return 0;
  }
}

uint8_t summary_testrange(SUMMARY *s, SUMMARY_VALUE lo, SUMMARY_VALUE hi, uint16_t options)
{                                                  // generic range of elements test
  SUMMARY_VALUE i;

  if (s == NULL)
    return 0;

  for (i = lo; i <= hi; i++)
    if (summary_test(s, i, options))
      return 1;

  return 0;    
}

void summary_add(SUMMARY *s, SUMMARY_VALUE v)         // generic summary element add 
{
  int i;
  SUMMARY s1;

  if (s == NULL)
    return;

  if (s->count < SUMMARY_LEN && summary_test(s, v, 0))
    return;

  if (s->count < SUMMARY_LEN)
    s->summary[s->count++] = v;
  else {
    if (s->count == SUMMARY_LEN)
    {
      summary_init(&s1, s->type, s->options);
      for (i = 0; i < s->count; i++)
        summary_addel(&s1, s->summary[i]);
      memcpy(s->summary, s1.summary, sizeof(s->summary));
    }

    summary_addel(s, v);
  }
}

void summary_mergeor(SUMMARY *s1, SUMMARY *s2, SUMMARY *s3)     // merging method for two Bloom filters or two exist histograms
{
  int i;

  for (i = 0; i < SUMMARY_LEN; i++)
    s3->summary[i] = s1->summary[i] | s2->summary[i];
}

void summary_mergertree(SUMMARY *s1, SUMMARY *s2, SUMMARY *s3)     // merging for two RTrees
{
  uint8_t a, b, c, d, x, y, z, w;

  a = s1->summary[0] & 0xff; b = s1->summary[0] >> 8;
  c = s1->summary[1] & 0xff; d = s1->summary[1] >> 8;
  x = s2->summary[0] & 0xff; y = s2->summary[0] >> 8;
  z = s2->summary[1] & 0xff; w = s2->summary[1] >> 8;

  s3->summary[0] = MIN(a, x) | (MIN(b, y) << 8);
  s3->summary[1] = MAX(c, z) | (MAX(d, w) << 8);
}

void summary_mergechistogram(SUMMARY *s1, SUMMARY *s2, SUMMARY *s3)  // merging for two count histograms
{
  int i;
  uint16_t s[SUMMARY_SIZE];
  uint8_t normalize = 0;

  for (i = 0; i < SUMMARY_SIZE; i++)
  {
    s[i] = (uint16_t)((uint8_t *) s1->summary)[i]+((uint8_t *) s2->summary)[i];
    if (s[i] > 0xff)
      normalize = 1;
  }

  if (normalize)
    for (i = 0; i < SUMMARY_SIZE; i++)
    {
      if (s[i] > 1)
        ((uint8_t *) s3->summary)[i] = (s[i] >> 1);
    }
  else for (i = 0; i < SUMMARY_SIZE; i++)
    ((uint8_t *) s3->summary)[i] = s[i];
}

void summary_domerge(SUMMARY *s1, SUMMARY *s2, SUMMARY *s3)   // merging if summaries are not lists
{
  s3->count = s1->count+s2->count;

  switch (s3->type)
  {
    case SUMMARY_BLOOMFILTER:    summary_mergeor(s1, s2, s3);         break;
    case SUMMARY_RTREE:          summary_mergertree(s1, s2, s3);      break;
    case SUMMARY_COUNTHISTOGRAM: summary_mergechistogram(s1, s2, s3); break;
    case SUMMARY_EXISTHISTOGRAM: summary_mergeor(s1, s2, s3);         break;
  }
}

void summary_merge(SUMMARY *s1, SUMMARY *s2)               // generic summary merging
{
  int i;
  SUMMARY s3;

  if (s1 == NULL || s2 == NULL)
    return;

  if (s1->type != s2->type || s1->options != s2->options)
    return;

  summary_init(&s3, s1->type, s1->options);

  if (s1->count <= SUMMARY_LEN && s2->count <= SUMMARY_LEN)
  {
    for (i = 0; i < s1->count; i++)
      summary_add(&s3, s1->summary[i]);
    for (i = 0; i < s2->count; i++)
      summary_add(&s3, s2->summary[i]);
  } else if (s1->count > SUMMARY_LEN && s2->count <= SUMMARY_LEN) {
    memcpy(&s3, s1, sizeof(SUMMARY));
    for (i = 0; i < s2->count; i++)
      summary_add(&s3, s2->summary[i]);
  } else if (s1->count <= SUMMARY_LEN && s2->count > SUMMARY_LEN) {
    memcpy(&s3, s2, sizeof(SUMMARY));
    for (i = 0; i < s1->count; i++)
      summary_add(&s3, s1->summary[i]);
  } else if (s1->count > SUMMARY_LEN && s2->count > SUMMARY_LEN)
    summary_domerge(s1, s2, &s3);

  memcpy(s1, &s3, sizeof(SUMMARY));
}

uint8_t summary_equal(SUMMARY *s1, SUMMARY *s2)
{
  int i;

  if (s1 == NULL || s2 == NULL || s1->type != s2->type || s1->options != s2->options ||
    ((s1->count <= SUMMARY_LEN) ^ (s2->count <= SUMMARY_LEN)))
    return 0;

  if (s1->count <= SUMMARY_LEN)
  {
    if (s1->count != s2->count)
      return 0;

    for (i = 0; i < s1->count; i++)
      if (summary_test(s2, s1->summary[i], 0) == 0)
        return 0;

    return 1;
  } else
    return (memcmp(s1->summary, s2->summary, SUMMARY_SIZE) == 0);
}

void summary_print(SUMMARY *s)        // display summary for debugging
{
  char ss[256];

  if (s == NULL)
    return;

  print_hexlist(ss, (uint8_t *) s->summary, sizeof(s->summary));
  DBGOUT("%d, %d, %d, %s", s->type, s->options, s->count, ss);
}




